package com.demo.java.OD301_350.OD347;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【树状结构查询(B卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146162956
 */
public class OdMain {
        public static void main(String[] args) {
            // 创建Scanner对象，读取输入
            Scanner scanner = new Scanner(System.in);

            // 读取输入的树的节点数量
            int n = scanner.nextInt();
            scanner.nextLine();  // 读取换行符

            // 创建一个Map来表示树，key是父节点，value是该节点的所有子节点
            Map<String, List<String>> tree = new HashMap<>();

            // 读取每个父子节点关系
            for (int i = 0; i < n; i++) {
                String inputTemp = scanner.nextLine();  // 读取父子节点关系的输入
                List<String> temp = splitStr(inputTemp); // 将输入的字符串分割成列表
                String a = temp.get(0);  // 父节点
                String b = temp.get(1);  // 子节点

                // 将子节点加入父节点的子节点列表中，使用computeIfAbsent方法保证父节点的子节点列表存在
                tree.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
            }

            // 读取要查询的目标节点
            String target = scanner.nextLine();

            // 获取目标节点的所有子节点
            List<String> childrens = new ArrayList<>(tree.get(target));
            // 存储最终的结果（按字典序排列的所有子节点）
            List<String> result = new ArrayList<>();

            // 遍历所有的子节点，使用广度优先搜索（BFS）
            while (!childrens.isEmpty()) {
                String node = childrens.get(0);  // 取出当前的子节点
                childrens.remove(0);  // 从队列中移除该节点
                result.add(node);  // 将当前子节点加入结果列表

                // 如果当前子节点有子节点，继续将其加入待处理队列
                if (tree.containsKey(node)) {
                    for (String x : tree.get(node)) {
                        childrens.add(x);  // 将该子节点的子节点加入队列
                    }
                }
            }

            // 对结果进行字典序排序
            Collections.sort(result);
            // 输出所有结果
            for (String res : result) {
                System.out.println(res);
            }
        }

        // 该函数用于将输入的字符串按空格分割，转换为整型列表（此函数并未被实际调用）
        public static List<Integer> split(String paramsStr) {
            List<Integer> p = new ArrayList<>();
            int start = 0;
            int end = paramsStr.indexOf(' ');  // 查找空格
            // 遍历字符串，按空格分割并转换为整数
            while (end != -1) {
                p.add(Integer.parseInt(paramsStr.substring(start, end)));
                start = end + 1;
                end = paramsStr.indexOf(' ', start);
            }
            p.add(Integer.parseInt(paramsStr.substring(start)));  // 添加最后一个数字
            return p;
        }

        // 该函数用于将输入的字符串按空格分割，转换为字符串列表
        public static List<String> splitStr(String paramsStr) {
            List<String> p = new ArrayList<>();
            int start = 0;
            int end = paramsStr.indexOf(' ');  // 查找空格
            // 遍历字符串，按空格分割
            while (end != -1) {
                p.add(paramsStr.substring(start, end));  // 获取当前子字符串并添加到列表中
                start = end + 1;
                end = paramsStr.indexOf(' ', start);
            }
            p.add(paramsStr.substring(start));  // 添加最后一个子字符串
            return p;
        }

}